package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-22 13:05
 **/
public class LeetCode686 {

    public int repeatedStringMatch(String a, String b) {
        int m = a.length();
        int n = b.length();

        int index = strStr(a, b);
        if (index == -1) {
            return -1;
        }

        if (m - index >= n) {
            return 1;
        }

        //如果要叠加一次以上的话,那么两边至少需要2次,然后就是看中间是否还有
        return (n + index - m - 1) / m + 2;
    }

    //kmp算法,返回匹配开始的索引
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();

        if (n == 0) {
            return -1;
        }

        int[] next = getNext(needle);

        for (int i = 0, j = 0; i - j < m; ++i) {
            while (j > 0 && haystack.charAt(i % m) != needle.charAt(j)) {
                j = next[j - 1];
            }

            if (haystack.charAt(i % m) == needle.charAt(j)) {
                ++j;
            }

            if (j == n) {
                return i - n + 1;
            }
        }

        return -1;
    }

    int[] getNext(String str) {
        int m = str.length();
        int[] next = new int[m];

        for (int i = 0, j = 1; j < m; ++j) {
            while (i > 0 && str.charAt(j) != str.charAt(i)) {
                i = next[i - 1];
            }

            if (str.charAt(i) == str.charAt(j)) {
                ++i;
            }

            next[j] = i;
        }

        return next;
    }




    public static void main(String[] args) {
        LeetCode686 code = new LeetCode686();
        System.out.println(code.repeatedStringMatch("aaaaaaaaaaaaaaaaaaaaaabba", "ba"));
    }

}
